from typing import List
from unittest import TestCase


def first_value_gt(lst: List[int], value: int, start: int = None, end: int = None):
    """
    二分查找: 求大于value的第一个数的位置
    :param lst: 数组  需要是严格升序排列的
    :param value: 值
    :param start: 搜索的起始范围
    :param end: 搜索的结束范围, 不包括end
    :return:
    如果没有找到: 返回index为min(len(lst), end)
    否则范围第一个大于value数的位置
    """
    if not start:
        start = 0
    else:
        start = max(0, start)
    if not end:
        end = len(lst)
    else:
        end = min(len(lst), end)

    # 求min{k | lst[k] > value, start <= k <= end }
    i, j = start, end
    while i < j:
        m = (i + j) // 2
        if lst[m] <= value:
            i += 1
        else:
            j = m
    return i


# 求大于等于value的第一个数的位置:
def first_value_gteq(value: int, lst: List[int], start: int, end: int):
    # 求min{k | lst[k] > value, start <= k <= end }
    i, j = start, end
    while i < j:
        m = (i + j) // 2
        if lst[m] < value:
            i += 1
        else:
            j = m
    return i


class BinarySearch(TestCase):
    def test_first_value_gt(self):
        assert first_value_gt([0, 1, 2, 5, 6, 7, 9, 12], 7) == 6
        # 如果没有大于value的值, 此时返回结果为len(lst)
        assert first_value_gt([0, 1, 2, 5, 6, 7, 9], 10) == len([0, 1, 2, 5, 6, 7, 9])
        # 结果在最后一位时
        assert first_value_gt([0, 1, 2, 5, 6, 7, 9, 12], 10) == len([0, 1, 2, 5, 6, 7, 9, 12]) - 1
        # 结果在第一位时
        assert first_value_gt([3, 5, 6, 7, 9, 12], 2) == 0
        # 如果lst为空, 此时没有大于5的元素, 返回len(lst)
        assert first_value_gt([], 5) == 0


if __name__ == '__main__':
    BinarySearch().test_first_value_gt()
